Concurs CSC 1995, Problema B

Baraj (lotul mic), ziua2, problema 3 (Grasanul)
Bucuresti, 28.05.1996
-------------------------------------
	Unii din noi pot fi destul de norocosi ca sa poata trece prin cea mai 
mica gaura; altii nu. Un drum de la A la B intr-un supermarket (chiar fara un 
carucior) poate fi destul de dificil si sa solicite destul de multa abilitate.
Sa consideram intr-un mod abstract aceasta problema a trecerii prin magazin: 
fiind dat un culoar de o anumita largime, cu obstacole imprastiate prin el, 
aratati cum poate o persoana grasa sa-l parcurga intrand prin capatul stang al 
culoarului si iesind prin cel din dreapta. Consideram ca, vazuta de sus, o 
persoana grasa arata ca un cerc, si ca ea este incompresibila (o persoana cu 
diametrul d nu poate trece printre doua obstacole aflate la o distanta mai mica
dacat d).
Intrare:
	Prima linie a fisierului de intrare GRASAN.INP specifica numarul N de 
date de test care trebuie prelucrate de program. Intrarea pentru fiecare test 
consta din urmatoarele linii:

L W    - L (0<=L<=100) este lungimea culoarului, W (0<=W<=100) - largimea lui;
O      - O (0<=O<=100) reprezinta numarul de obstacole din culoar;
X1 Y1
X2 Y2  - (Xi Yi), 0<=Xi<=L,0<=Yi<=W reprezinta coordonatele unui obstacol
....
XO YO

	Toate datele sunt numere intregi.

Iesire:
Pentru fiecare test se tipareste pe ecran o linie de forma:

"Marimea maxima in testul t este M"

unde t (1<=t<=N) este numarul testului, iar M este un numar real cu 4 cifre
zecimale care da diametrul maxim al unei persoane care poate reusi sa treaca
prin culoar in testul respectiv.

Exemplu: Pentru intrarea:
1
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1

iesirea este:

Marimea maxima in testul 1 este 2.2361

Timp limita pentru fiecare test: 30 secunde
==============================================

Solutie (Marinel Serban):
uses crt;
var i,j : byte;
    a : array[1..100,1..100] of char;
    f,g : text;
    numefis : string;
    n, m : byte;
    o : byte;
    x,y : byte;
begin
   clrscr;
   write('Nume fisier intrare : '); readln(numefis);
   assign(f,numefis);
   reset(f);
   write('Nume fisier iesire : '); readln(numefis);
   assign(g,numefis);
   rewrite(g);
   readln(f,n,m);
   readln(f,o);
   for i := 1 to n do
      for j := 1 to m do
         a[i,j] := '.';
   for i := 1 to o do
       begin
          readln(f,x,y);
          a[x,y] := 'o';
       end;
   clrscr;
   for j:= m downto 1 do
       begin
           for i := 1 to n do write(g,a[i,j]);
           writeln(g)
       end;
       writeln(g,#12);
   close(f);
   close(g)
end.
-----------------------------------------
Teste:
6
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1
8 5
8
1 2
1 3
2 1
2 2
2 4
3 2
3 3
4 4
20 13
32
1 1
1 12
2 2
2 11
2 9
3 4
3 6
5 2
5 5
5 7
5 11
6 3
6 10
7 5
7 7
7 13
8 10
9 5
10 8
11 1
12 4
12 6
13 1
14 6
15 3
16 6
16 8
17 3
18 10
19 5
19 7
20 10
100 1
0
100 1
10
1 1
10 1
20 1
30 1
40 1
50 1
60 1
70 1
80 1
90 1
100 1
17 15
35
2 11
2 14
3 4
3 7
3 9
3 11
4 2
4 5
5 13
6 4
6 8
6 9
6 10
6 11
7 4
7 7
7 13
8 7
8 13
9 4
9 10
9 13
10 4
10 10
10 13
11 6
11 8
11 13
12 8
13 8
13 12
14 8
14 11
15 8
15 11
--------------------------
Solutia 2 (Cristian Cadar - Bucuresti)
{ Programare dinamic - vezi Curs Marius Vlad }
uses crt;
type
   ref=^matrice;
   matrice=array[0..100,0..100] of real;
   punct=record x,y:real end;
var
   a:array[0..101,0..101] of byte;
   t:ref;
   f:text;
   st:string;
   i1,j1,i,j,k,l,o,n,m:integer;
   d_max,max:real;
   aa,bb,cc,dd:punct;

procedure citire;
begin
     clrscr;
     write('Fisier intrare:');
     readln(st);
     assign(f,st);
     reset(f);
     readln(f,m,n);
     readln(f,o);
     fillchar(a,sizeof(a),0);
     for k:=1 to o do
         begin
              readln(f,i,j);
              a[j,i]:=1;
         end;
     close(f);
end;

function min(a,b:real):real;
begin
     if a<b
        then min:=a
        else min:=b;
end;

function dist(a,b:punct):real;
begin
     dist:=sqrt( sqr(a.x-b.x)+sqr(a.y-b.y) );
end;

procedure dinamic;
begin
     new(t);
     fillchar(t^,sizeof(t^),0);
     for i:=1 to m do
         begin
              a[0,i]:=1;
              a[n,i]:=1;
         end;
     for i:=0 to n-1 do
         if a[i,1]=1
            then
                begin
                     k:=i+1;
                     while a[k,1]<>1 do
                       inc(k,1);
                     t^[i,1]:=k-i;
                end;
     for k:=2 to m do
         begin
              for i:=0 to n-1 do
                  if a[i,k]=1
                     then
                         begin
                              i1:=i+1;
                              while a[i1,k]=0 do
                                inc(i1);
                              max:=0;
                              for j:=0 to n-1 do
                                  if a[j,k-1]=1
                                     then
                                         begin
                                              j1:=j+1;
                                              while a[j1,k-1]=0 do
                                                inc(j1);
                                              aa.x:=k;aa.y:=i;
                                              bb.x:=k;bb.y:=i1;
                                              cc.x:=k-1;cc.y:=j;
                                              dd.x:=k-1;dd.y:=j1;
                                              d_max:=min(t^[j,k-1],min(dist(aa,bb),min( dist(cc,bb),dist(aa,dd) ) ) );
                                              if d_max>max
                                                 then max:=d_max;
                                         end;
                              t^[i,k]:=max;
                         end;
         end;
     max:=0;
     for i:=0 to n do
         if max<t^[i,m]
            then max:=t^[i,m];
     writeln(max:6:4);
     readkey;
end;

begin
     citire;
     dinamic;
end.
----------------------------
